import org.omg.CORBA.INTERNAL;
import sun.security.ec.point.AffinePoint;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution279 {
    /**
     * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
     */

    // dp
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        int maxIndex = (int)Math.sqrt(n) + 1;
        int[] squareNums = new int[maxIndex];
        for (int i = 1; i < maxIndex; i++) {
            squareNums[i] = i * i;
        }

        for (int i = 1; i <= n; i++){
            for (int j = 1; j < maxIndex; j++) {
                if (i < squareNums[j]) break;
                dp[i] = Math.min(dp[i], dp[i - squareNums[j]] + 1);
            }
        }
        return dp[n];
    }

}
